package leetcode.code1646.GetMaximuminGeneratedArray;

public class Solution164601 extends GetMaximuminGeneratedArray {

//	nums[0] = 0
//	nums[1] = 1
//	当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
//	当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

	@Override
	public int getMaximumGenerated(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int[] array = new int[n + 1];
		array[0] = 0;
		array[1] = 1;
		int max = 1;
		for (int i = 1; i <= n / 2; i++) {
			if (i * 2 <= n) {
				array[i * 2] = array[i];
				max = Math.max(max, array[i]);
			}
			if (i * 2 + 1 <= n) {
				array[i * 2 + 1] = array[i] + array[i + 1];
				max = Math.max(max, array[i * 2 + 1]);
			}
		}
		return max;
	}

	public static void main(String[] args) {
		Solution164601 so = new Solution164601();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
		so.debug5();
	}

}
